﻿using System;
class Prob4BinaryDigitsCount
{
    static void Main()
    {
        byte binaryDigit;
        byte numberOfZeros;
        byte numberOfOnes;
        long mask;
        long currentBit;
        int numberOfNums;
        uint digitN;
        binaryDigit = byte.Parse(Console.ReadLine());
        numberOfNums = int.Parse(Console.ReadLine());
        int[] result = new int[numberOfNums];
        for (int i = 0; i < numberOfNums; i++)
        {
            numberOfOnes = 0;
            numberOfZeros = 0;
            digitN = uint.Parse(Console.ReadLine());
            for (int j = 31; j >= 0; j--)
            {
                mask = 1 << j;
                currentBit = ((digitN & mask) >> j);
                if (currentBit == 1)
                {
                    numberOfOnes++;
                }
                else
                {
                    if (numberOfOnes > 0)
                    {
                        numberOfZeros++;
                    }
                }
                if (binaryDigit == 1)
                {
                    result[i] = numberOfOnes;
                }
                else
                {
                    result[i] = numberOfZeros;
                }
            }
        }
        for (int k = 0; k < numberOfNums; k++)
        {
            Console.WriteLine(result[k]);
        }
    }
}

